Woda

Limit pamięci: 32 MB

Na prostokątnej szachownicy składającej się pól ustawiono prostopadłościanów --- na każdym polu jeden prostopadłościan. Podstawa każdego prostopadłościanu pokrywa się z jednym polem szachownicy i ma powierzchnię jednego cala kwadratowego. Prostopadłościany na sąsiednich polach ściśle przylegają do siebie i nie tworzą żadnych szczelin. Na tę konstrukcję spadł ulewny deszcz. W niektórych miejscach utworzyły się zastoiska wody.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia rozmiary szachownicy oraz wysokości prostopadłościanów ustawionych na poszczególnych polach,
• obliczy maksymalną objętość wody, która po deszczu może pozostać w zastoiskach,
• wypisze wyniki na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia są zapisane dwie dodatnie liczby całkowite i , , . Są to rozmiary szachownicy. W każdym z kolejnych wierszy znajduje się liczb całkowitych z przedziału . -ta liczba w -tym wierszu jest wyrażoną w calach wysokością prostopadłościanu stojącego na przecięciu -tej kolumny i -tego wiersza szachownicy.

Wyjście

Twój program powinien zapisać w pierwszym i jedynym wierszu standardowego wyjścia jedną liczbę całkowitą równą maksymalnej objętości wody (wyrażoną w calach sześciennych), która może zebrać się w zastoiskach konstrukcji.

Przykład

Dla danych wejściowych:

3 6
3 3 4 4 4 2
3 1 3 2 1 4
7 3 1 6 4 1

poprawną odpowiedzią jest:

5

Poniższy rysunek przedstawia szachownicę przed i po deszczu (widok z góry). Szare pola oznaczają zastoiska.

Autor zadania: Grzegorz Jakacki.